package nachos.threads;

import java.util.Comparator;
import java.util.PriorityQueue;

import sun.misc.Compare;
import nachos.machine.*;

/**
 * Uses the hardware timer to provide preemption, and to allow threads to sleep
 * until a certain time.
 */
public class Alarm {
	/**
	 * Allocate a new Alarm. Set the machine's timer interrupt handler to this
	 * alarm's callback.
	 * 
	 * <p>
	 * <b>Note</b>: Nachos will not function correctly with more than one alarm.
	 */
	public Alarm() {
		Machine.timer().setInterruptHandler(new Runnable() {
			public void run() {
				timerInterrupt();
			}
		});
	}

	/**
	 * The timer interrupt handler. This is called by the machine's timer
	 * periodically (approximately every 500 clock ticks). Causes the current
	 * thread to yield, forcing a context switch if there is another thread that
	 * should be run.
	 */
	public void timerInterrupt() {
		// gurantee atomicity
		boolean intStatus = Machine.interrupt().disable(); 
		long nowTime = Machine.timer().getTime();
		
		while(waitingQueue.size()!=0 && waitingQueue.peek().time <= nowTime){
			// poll the top thread from waiting queue, and then put it to the ready queue
			KThread top = waitingQueue.poll().kthread;
			if(top!=null)
				top.ready();
		}
		// Causes the current thread to yield
		KThread.yield();
		
		Machine.interrupt().restore(intStatus);
	}

	/**
	 * Put the current thread to sleep for at least <i>x</i> ticks, waking it up
	 * in the timer interrupt handler. The thread must be woken up (placed in
	 * the scheduler ready set) during the first timer interrupt where
	 * 
	 * <p>
	 * <blockquote> (current time) >= (WaitUntil called time)+(x) </blockquote>
	 * 
	 * @param x the minimum number of clock ticks to wait.
	 * 
	 * @see nachos.machine.Timer#getTime()
	 */
	public void waitUntil(long x) {
		// gurantee atomicity
		boolean intStatus = Machine.interrupt().disable(); 
		
		long wakeTime = Machine.timer().getTime() + x;

		// add current thread which are prior to set time to waiting queue.
		waitingQueue.add(new ThreadWrapper(KThread.currentThread(), wakeTime));
		KThread.sleep();
		Machine.interrupt().restore(intStatus);
		
	}
	
	// waiting queue for each added thread ordered in the timely sequence
	private static PriorityQueue<ThreadWrapper> waitingQueue = new PriorityQueue<ThreadWrapper>(10, new Comparator<ThreadWrapper>() {
		public int compare(ThreadWrapper w1, ThreadWrapper w2) {
			return w1.time <= w2.time? -1 : 1;
		}
	});
}

// thread with time
class ThreadWrapper{
	KThread kthread;
	long time;
	ThreadWrapper(KThread kthread, long time){
		this.time = time;
		this.kthread = kthread;
	}
}

